1. Field of the Invention
The present invention is directed to technology relevant to decoding Low Density Parity codes.
2. Description of the Related Art
Communication technology has become more important and has received greater attention as more people communicate via computer networks, telephone networks and various wireless networks. The goal is to communicate data in a reliable and efficient manner. However, data being communicated can be corrupted. For example, wireless data (e.g. digital or analog, voice or non-voice) is subject to noise.
There are two broad classes of solutions for insuring that data is communicated accurately. First, there is ARQ, which includes re-transmitting data if there is a problem. Second, there is Forward Error Correction (FEC), which includes using codes with the data to detect and, possibly, correct, corrupt data.
The problem being solved with FEC is how much redundancy to add in an intelligent manner to make sure that the data arrives correctly. Long codes do a better job insuring correctness, but are more complex and harder to work with. Thus, most codes used are shorter codes operating on smaller block lengths.
There are at least two classes of larger codes being used for FEC: Turbo codes and Low Density Parity Codes (LDPC). Low Density Parity Codes were proposed by Gallager in the early 1960s. R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, January 1962. The structure of Gallager's codes (uniform column and row weight) led them to be called regular LDPC codes. Gallager provided simulation results for codes with block lengths on the order of hundreds of bits. However, these codes were too short for the sphere packing bound to approach Shannon capacity, and the computational resources for longer random codes were decades away from being broadly accessible.
Following the groundbreaking demonstration by Berrou et al. (C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo codes,” in Proc. IEEE Int. Conf. Commun., Geneva, Switzerland, May 1993, pp. 1064-1070) of the impressive capacity-approaching capability of long random linear (turbo) codes, MacKay (D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, pp. 399-431, March 1999) re-established interest in LDPC codes during the mid to late 1990s. Luby et al (M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, “Improved low-density parity-check codes using irregular graphs,” IEEE Trans. Inform. Theory, vol. 47, pp. 585-598, February 2001) formally showed that properly constructed irregular LDPC codes can approach capacity more closely than regular codes. Richardson, Shokrollahi and Urbanke (T. Richardson, A. Shokrollahi, and R. Urbanke, “Design of capacity approaching irregular low density parity check codes,” IEEE Trans. on Inform. Theory, vol. 47, pp. 618-637, February 2001) created a systematic method called density evolution to analyze and synthesize the degree distribution in asymptotically large random bipartite graphs under a wide range of channel realizations.
In his original work, Gallager also introduced several decoding algorithms. One of these algorithms has since been identified for general use in factor graphs and Bayesian networks (J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Francisco, Calif.: Morgan Kaufmann, 1998) and is often generically described as Belief Propagation (BP). In the context of LDPC decoding, messages handled by a belief propagation decoder represent probabilities that a given symbol in a received codeword is either a one or a zero. These probabilities can be represented absolutely, or more compactly in terms of likelihood ratios or likelihood differences. The logarithmic operator can also be applied to either of these scenarios. Due to the complexity of the associated operator sets and word length requirements, the log-likelihood ratio form of the Sum-Product algorithm is the form that is best suited to VLSI implementation. However, this form still posses significant processing challenges as it employs a non-linear function that must be represented with a large dynamic range for optimal performance. Throughout the rest of the document, unaltered log-likelihood belief propagation with the described as Full BP.
FIGS. 9-14 depict bipartite graphs, which include variable nodes and constraint nodes. FIGS. 15-31 depict the use of bipartite graphs for massage passing decoding.
Even Full-BP algorithms suffer performance degradation as compared to the optimum Maximum Likelihood (ML) decoder for a given code. This is due to the fact that bipartite graphs representing finite-length codes without singly connected nodes are inevitably non-tree-like. Cycles in bipartite graphs compromise the optimality of belief propagation decoders. The existence of cycles implies that the neighbors of a node are not in general conditionally independent (given the node), therefore graph separation does not hold and Pearl's polytree algorithm (J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Francisco, Calif.: Morgan Kaufmann, 1998) (which is analogous to Full-BP decoding) inaccurately produces graph a-posteriori probabilities. Establishing the true ML performance of LDPC codes with length beyond a few hundred bits is generally viewed as an intractable problem. However, code conditioning techniques (T. Tian, C. Jones, J. Villasenor, and R. D. Wesel, “Characterization and selective avoidance of cycles in irregular LDPC code construction,” International Conference on Communications (ICC) 2003) can be used to mitigate the non-optimalities of iterative decoders and performance that approaching the Shannon capacity is achievable even with the presence of these decoding non-idealities.